Pedigrees, or family trees, are graphs of family relationships that are usedto study inheritance. A fundamental problem in computational biology is tofind, for a pedigree with $n$ individuals genotyped at every site, a set ofMendelian-consistent haplotypes that have the minimum number of recombinations.This is an NP-hard problem and some pedigrees can have thousands of individualsand hundreds of thousands of sites. This paper formulates this problem as a optimization on a graph andintroduces a tailored algorithm with a running time of O(n^{(k+2)}m^{6k}) for nindividuals, m sites, and k recombinations. Since there are generally only 1-2recombinations per chromosome in each meiosis, k is small enough to make thisalgorithm practically relevant.
展开▼
机译：家谱或家族树是用于研究继承的家族关系图。对于在每个位点进行基因分型的$ n $个体谱系，发现其生物学上的一个基本问题是一组具有最小重组数量的一致的孟德尔一致性单倍型。这是一个NP难题，有些谱系可以有成千上万个个人和成千上万的网站。本文将此问题描述为图上的优化，并针对个人，m个位置和k个重组引入了运行时间为O（n ^ {（k + 2）} m ^ {6k}）的量身定制算法。由于每个减数分裂中每个染色体通常只有1-2个重组，因此k足够小，可以使该算法在实践中有意义。
展开▼
